The present invention relates generally to a method, system, and apparatus for improving performance of a program executing on a computer system. More particularly the present invention improves the balance determined by an ordering of information stored in a tree-based data structure on a computer and thereby reduces the time required to search, update, or perform other common operations on the tree-based data structure on a computer system.
Typically a tree-based data structure is used to store information in a computer system. It will be appreciated that the term xe2x80x9ctree-based data structurexe2x80x9d as used herein represents connected information that includes xe2x80x9cnodesxe2x80x9d that are individual units of information and that include at least one value. Further, the connection of the nodes may represent a hierarchy in which the value of a node may be equal to, greater than, or less than another node. One implementation of a tree-based data structure, typically called a Binary Tree, represents the descendant nodes of a parent node having a value that is less than or equal to the parent node as left nodes, and the descendant nodes having a value greater than the parent node as right nodes. One form of the Binary Tree, typically called a Cartesian Tree, represents the descendant nodes of a parent node being associated with a second value less than or equal to the second value associated with the parent node. The terms xe2x80x9ctreexe2x80x9d and xe2x80x9ctree-based data structurexe2x80x9d will be used interchangeably herein.
Inserting a new node into an existing tree-based data structure may include the following operations. Initially, a search is conducted starting at the initial, or root, node and traversing down the tree until the correct position for insertion is located. At each node a direction, or branch, is followed depending on whether the new node value is equal to, less than, or greater than the existing node value. Then a proper location for insertion is determined based on the properties of the tree, such as the properties of a Binary Tree or a Cartesian Tree, and the relationship of the two nodes.
A problem with trees of the past, such as Binary Trees, is that nodes associated with equivalent values have not been specially handled by operations that manage a tree. It will be appreciated that the information stored in the tree-based data structure may be catalogued by reference to a value, typically called a key, and the key may be identical to other keys associated with the tree-based data structure. Therefore, since the operation of inserting a node in a tree proceeds to the same branch when the value associated with the new node is equal to the value associated with an existing node, the insertion of many new nodes will be on the same branch thereby leading to an imbalanced tree. It will be appreciated that an imbalanced tree has a preponderance of the nodes placed on the same branch of the tree.
Another problem with trees of the past, such as Cartesian Trees, occurs when the values associated with the nodes in a tree progress in a patterned order, since the related information in the tree will be imbalanced. For instance, when the values associated with the nodes progress sequentially, the representative node will generally be placed on the same branch of the tree as the previous node thus creating an imbalanced tree.
An important characteristic of a tree is that it enables quick searches of the nodes on the tree. Therefore, if the tree is imbalanced the tree may be considered a degenerate tree. The degenerate tree is characterized by a long search path, similar to a linked list, and information is reached by traversal of the nodes via the long search path. Those skilled in the art will appreciate the use of a linked list.
The operations of the past that operate to manage a tree by compact solutions do not efficiently manage the occurrence of equal keys that are associated with nodes or the occurrence of keys that are associated with nodes in a patterned order. Therefore, the resulting tree is degenerate and does not enable quick searching, updating, or performing other related operations on the tree. Also operations of the past may efficiently balance a tree but require expensive inefficient solutions to manage the tree.
The present invention is a method, system, and apparatus for improving performance of a program executing on a computer system. More particularly the present invention improves the balance determined by an ordering of information stored in a tree-based data structure on a computer by a compact solution thereby reducing the time required to search, update, or perform other common operations on the tree-based data structure.
The present invention specially handles operations that manage a tree to ensure that the tree is balanced. More particularly, when the key associated with a new node is equal to the key associated with another node in the tree, the present invention manages the operation of inserting the new node in a tree such that the tree is balanced. Further, when the values associated with the nodes in a tree progress in a patterned order, the present invention specially handles operations that manage a tree to ensure that the nodes in the tree are balanced.
The present invention novelly manages the operations of inserting a node in a tree by specially handling nodes with associated keys that are equal or nodes with associated keys that progress in a pattern. Thereby, the present invention reduces the occurrence of a degenerate tree during the operation of inserting nodes in a tree over tree-related operations in the past, and enables quick searching, updating, or other related operations on the tree. It will be appreciated that patterns associated with keys, such as sequentially progressing keys, may cause a degenerate tree.
The present invention novelly and efficiently compares at least two computer-based values by determining a bit reversal order value of a first value and a second value. The computer system includes computer readable medium that is encoded in a source program that executes on the computer system. Also, the computer system supports two""s complement execution of the source program, a logical XOR operation, and a logical AND operation, subtraction, and negation.
In one embodiment of the present invention a third value is assigned the result of executing logical XOR on the first value and the second value. Further, a fourth value is assigned the result of executing negation on the third value. In an alternative embodiment the third value is assigned the result of subtracting the second value from the first value; and the fourth value is assigned the result of subtracting the first value from the second value.
Then in either embodiment of the present invention, a fifth value is assigned a result of executing logical AND on the third value and the fourth value. Further, a bit reversal order value is assigned the result of executing logical AND on the fifth value and the second value, and if the bit reversal order value is not zero then the reverse of the second value is greater than the reverse of the first value thereby ordering the first value and the second value.
Accordingly, it is an object of the invention to balance the placement of nodes on a tree when the keys associated with the nodes are equal or when the keys associated with the nodes progress in a pattern. More particularly the present invention introduces a tie-breaking operation during the insertion of a node in a tree. The tie-breaking operation may be based on information that is associated with the node or associated with the location of the node.
Also, it is an object of the invention to improve the efficiency of searching, updating, and other associated operations of a node in a tree by using a bit reversal value or bit reversed address associated with the node to balance the tree. Typically, computer-based information is represented by bits in a computer system. A bit is a basic unit used to store information in a computer system. Therefore xe2x80x9cbit reversalxe2x80x9d refers to reversing each representative bit of a value so that the least significant bit becomes the most significant bit, the next-least significant bit becomes the next-most significant bit, and so on.
The bit reversal operation of the present invention advantageously uses the least significant bits of values associated with nodes in a tree. The least significant bits typically vary more than the most significant bits of values such as keys that may be associated with computer-based addresses. Therefore, the present invention introduces jitter into the values that are associated with nodes of a tree by a bit reversal operation that uses the least significant bits of the values. Thereby the present invention balances the nodes of a tree more efficiently than in the past. The term xe2x80x9cjitterxe2x80x9d refers herein to an irregular order of values as compared to a patterned order of values, that is used by the present invention to balance the values associated with nodes of a computer-based tree.
It is also an object of the invention to reduce the resources required to insert a node or to search for a node in a well-balanced tree by applying a bit-reversal operation to information associated with the node or the location of the node. More particularly, use of the bit reversal operation does not require the allocation of computer-based storage associated with each node and may be completed by operations in the computer registers during execution.
By means of example the present invention may be used to balance a degenerate Binary Tree by associating a second value with each node and organizing the tree as a Cartesian Tree. Further, the second value is the result of a bit-reversal operation of the present invention and introduces balance to an otherwise degenerate Binary Tree.
Another example of the use of the present invention associates a bit reversal order value with the result of the bit reversal operation that is applied to values associated with nodes of a tree thereby balancing a tree. A bit reversal value may be derived from the address of each node or the value associated with each node. Further the bit reversal value may be concatenated with the values associated with each node. Therefore an example of the use of the present invention operates as a tie-breaker by associating a bit reversal order value with nodes in a tree having a preponderance of nodes with equivalent values. Operating as a tie-breaker improves the balance of the tree by eliminating degeneracy caused by nodes having equivalent values.
By means of example of the use of a tree, an operating system (O.S.) typically includes information about computer-based resources used during the execution of instructions on a computer system. The information is often created in the form of a tree-based data structure. Therefore, the efficiency of execution of instructions on the computer system will be impacted by the efficiency of the allocation and use of the resources associated with the execution of the instruction. Further, the efficiency of searching, updating, or performing other computer-based operations on a tree-based data structure associated with the resources, will therefore impact the efficiency of the allocation and use of the resources, such as the execution of the instructions. The present invention creates a tree-based data structure with greater balance than in the past and thereby improves the efficiency of searching, updating, or performing other related operations on the tree-based data structure over past tree-based data structures.
Other aspects and advantages of the present invention will become apparent from the following detailed description, taken in conjunction with the accompanying drawings, illustrating by way of example the principles of the invention.